package TP3.ejercicio2;

import TP2.sorters.AbstractSorter;
import anaydis.sort.SorterType;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class QuickSorter extends AbstractSorter {

    int implementation, M;     //impl = 0 (u otro): Recursivo básico
                            //impl = 1: Recursivo con cut-off
                            //impl = 2: No Recursivo
                            //impl = 3: Media de Tres
                            //impl = 4: Three-way Partitioning

    public QuickSorter(){
        this(SorterType.QUICK);
        implementation = 0;
        M = 0;
    }

    protected QuickSorter(final SorterType type){
        super(type);
    }

    public void setImpl(int i){
        implementation = i;
    }

    public void setM(int i){
        M = i;
    }

    public <T> void sort(Comparator<T> comparator, List<T> list){
        switch(implementation){
            case 1:
                cutoffSort(comparator, list, 0, list.size());
                break;

            case 2:
                nonRecursiveSort(comparator, list, 0, list.size());  //*
                break;

            case 3:
                medianOfThreeSort(comparator, list, 0, list.size());
                break;

            case 4:
                threeWaySort(comparator, list, 0, list.size());      //*
                break;

            default:
                recursiveSort(comparator, list, 0, list.size());
                break;
        }
    }

    protected <T> void recursiveSort(Comparator<T> comparator, List<T> list, int min, int max){
        if(max <= min) return;
        int i = partition(comparator, list, min, max);
        recursiveSort(comparator, list, min, i-1);
        recursiveSort(comparator, list, i+1, max);
    }

    protected <T> int partition(Comparator<T> comparator, List<T> list, int min, int max){
        int i = min;
        int j = max;

        while(true){
            while(greater(comparator, list, list.size(), i++)){
                if(i == max) break;
            }
            while(greater(comparator, list, j--, list.size())){
                if (j == min) break;
            }
            if(i >= j) break;
            swap(list, i, j);
        }
        swap(list, i, max);
        return i;
    }

    protected <T> void cutoffSort(Comparator<T> comparator, List<T> list, int min, int max){
        if(max-min <= M) return;
        if(max <= min) return;
        int i = partition(comparator, list, min, max);
        cutoffSort(comparator, list, min, i-1);
        cutoffSort(comparator, list, i+1, max);
    }

    protected <T> void nonRecursiveSort(Comparator<T> comparator, List<T> list, int min, int max){
        List<Integer> pivots = new ArrayList<Integer>();
        pivots.add(0);
        pivots.add(list.size());
        int i = 0;
        while((i*2)+1<pivots.size()){
            if(Math.abs(pivots.get((2*i)+1) - pivots.get(2*i)) > 2){
                int g = nRPartition(comparator, list, pivots.get(2*i) , pivots.get((2*i)+1), (pivots.get((2*i)+1))-1);
                pivots.add(pivots.get(2*i));
                pivots.add(g);
                pivots.add(g);
                pivots.add(pivots.get((2*i)+1));
            }
            i++;
        }
    }

    protected <T> int nRPartition(Comparator<T> comparator, List<T> list, int min, int max, int pivot){
         int i = min;
        int j = max-2;
        boolean end = false;
        swap(list, pivot, max-1);
        pivot = max-1;
        do{
            boolean iGreater = false;
            do{
                if (!greater(comparator, list, i, pivot)) {
                    i++;
                } else {
                    iGreater = true;
                }
            }while((!iGreater) && (i < (j + 1)));
                boolean jLesser = false;
                do{
                    if (greater(comparator, list, j, pivot)) {
                        j--;
                    } else {
                        jLesser = true;
                    }
                }while((!jLesser) && i<j+1);
                if(i<j){
                    swap(list, i, j);
                }
                else{
                    swap(list,i,pivot);
                    end = true;
                }
        }while(!end);
        return i;
    }

    protected <T> void medianOfThreeSort(Comparator<T> comparator, List<T> list, int min, int max){
        if(greater(comparator, list, max-2, max-1)) swap(list, max-2, max-1);
        if(greater(comparator, list, max-1, max)) swap(list, max-1, max);
        if(greater(comparator, list, max-2, max-1)) swap(list, max-2, max-1);
        swap(list, max-1, max);
        recursiveSort(comparator, list, min, max);
    }

    protected <T> void threeWaySort(Comparator<T> comparator, List<T> list, int min, int max){
        if (min >= max){
            return;
        }
        int i = min;
        int j = max;
        int p = min;
        int q = max;
        int pivot = ((min + max) / 2);
                while (i < j) {
                    while (greater(comparator, list, pivot, i)) {
                        i++;
                    }
                    while (greater(comparator, list, j, pivot)) {
                        j--;
                    }
                    if (j == min) {
                        break;
                    }
                    if (i >= j) {
                        break;
                    }

                    if (i < j) {
                        swap(list, i, j);
                    }
                    if (equals(comparator, list, i, pivot)) {
                        p++;
                        swap(list, p, i);
                    }
                    if (equals(comparator, list, j, pivot)) {
                        q--;
                        swap(list, q, j);
                    }
                }
                swap(list, min, max);


                for (int k = min; k < p; k++, i--) {
                    swap(list, k, i);
                }
                for (int k = max; k > q; k--, j++) {
                    swap(list, j, k);
                }

    }

}
